#include "main/utils.h"
using namespace std;

int minPath1(const vector<vector<int>> cost) {
  int row = cost.size();
  vector<vector<int>> dp;
  dp.resize(row);
  for (int i = 1; i <= row; ++i) {
    dp[i - 1].resize(i);
  }
  dp[0][0] = cost[0][0];
  for (int i = 1; i < row; ++i) {
    dp[i][0] = dp[i - 1][0] + cost[i][0];
    for (int j = 1; j <= i; ++j) {
      if (j < i) {
        dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + cost[i][j];
      } else {
        dp[i][j] = dp[i - 1][j - 1] + cost[i][j];
      }
    }
  }

  int min_path = dp[row - 1][0];
  for (int i = 1; i < dp.back().size(); ++i) {
    if (dp[row - 1][i] < min_path) {
      min_path = dp[row - 1][i];
    }
  }

  return min_path;
}

int minPath2(const vector<vector<int>> cost) {
  int row = cost.size();
  vector<int> dp(row, 0);
  for (int i = 0; i < row; ++i) {
    for (int j = i; j >= 0; --j) {
      if (j == 0) {
        dp[j] = dp[j] + cost[i][j];
      } else if (j == i) {
        dp[j] = dp[j - 1] + cost[i][j];
      } else {
        dp[j] = min(dp[j - 1], dp[j]) + cost[i][j];
      }
    }
  }

  int min_path = dp[0];
  for (int i = 1; i < dp.size(); ++i) {
    if (dp[i] < min_path) {
      min_path = dp[i];
    }
  }

  return min_path;
}

int main() {
  vector<vector<int>> cost = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
  cout << minPath1(cost) << endl;
  cout << minPath2(cost) << endl;

  return 0;
}
